package dfs;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
public class 括号生成 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("输入n:");
        int n=sc.nextInt();
        List<String> strings = generateParenthesis(3);
        System.out.println(strings.toString());
    }
    static List<String> list = new ArrayList<String>();
    public static List<String> generateParenthesis(int n) {
       dfs(n,n,"");
       return list;
    }
    //left和right代表 还剩几个左（右）括号可用
    private static void dfs(int left, int right, String s) {
        if (left==0 && right==0){
            list.add(s);
            return;
        }
        if (left>0){
            dfs(left-1,right,s+"(");
        }
        if (right>left){
            dfs(left,right-1,s+")");
        }
    }
}
